1. Field of the Invention
The present invention relates to an image encoding and decoding apparatus for compressing and expanding image data and, more particularly, to an image data compression and expansion circuit for compressing and expanding encoded image data having a fixed data length.
The present invention also relates to an image encoding apparatus for compressing or expanding image data and, more particularly, to an image data compressing and expanding circuit for compressing and expanding encoded image data having a fixed data length.
The present invention further relates to an encoding method for compressing and expanding the data on a half tone image which is divided into blocks each having a small area.
2. Description of the Related Art
Methods of using input and output line buffers as a toggle have conventionally been proposed in order to increase the processing speed of the input and the output of image data. One such method is disclosed in Japanese Patent Laid-Open No. Sho 63-84270. The method disclosed in Japanese Patent Laid-Open No. Sho 63-84270 requires two line buffers 12, 13 of the same size, as shown in FIG. 20, in order to realize a toggle line buffer. This method is advantageous in that it is possible to process image data consecutively by reading image data from one line buffer 12 while writing image data into the other line buffer 13.
When image data is input or output from the line buffer 12 or 13, it is necessary to switch the line buffers 12 and 13 from one to the other by a data selector 16 every time the data for one line is input or output.
In order to apply the system of the conventional image processing apparatus having the above-described structure to a block encoding system, it is necessary to process the data for one line in a block as a unit. It is therefore necessary to provide the same number of input and output line buffers as the number of lines constituting one block. That is, twice as many line buffers as the lines constituting one block are required, and the increase in the number of line buffers unfavorably raises the cost of the image processing apparatus.
In addition, when the image data are read out of the line buffer, it is necessary not only to switch the line buffers for data in different blocks but for data for different lines within one block. The time assigned to the switching of the line buffers for data for different lines within one block is, under the severest condition, not longer than the time for which the image data for one pixel is transferred.
Furthermore, according to this method, if the image data transferring speed is higher than the response speed (reading speed of the FIFO) of the selector of the line buffer, the switching operation between the line buffers cannot overtake the data transferring operation. As a result, the output data of the adjacent line buffers collide with each other, so that high-speed image data compression-expansion is impossible.
Methods of editing encoded image data have conventionally been proposed. One such method is disclosed in Japanese Patent Laid-Open No. Hei 3-110914. FIG. 21 is a functional block diagram of the method disclosed in Japanese Patent Laid-Open No. Hei 3-110914. An image memory compresses the image data for one screen by a fixed length for each block, and the compressed image data are stored in the image memory consisting of one memory bank which is controlled by a one-system control signal. If the encoded data for one block is read and decoded as a unit, it is possible to edit the image data at the time of decoding.
In the conventional image data compressing method having the above-described structure, when the original image data are simultaneously encoded and decoded, access control is necessary for the operation of storing the encoded image data into the image memory and the operation of reading the encoded data from the image memory. It is therefore difficult to process the image data consecutively at a high speed, and the control method is complicated.
Methods of encoding image data which is divided into blocks each having a small area have conventionally been proposed. One such method is described in "Image Data Compressing Circuit for Hard Copy Apparatus", D-254 in the proceedings of the autumn meeting of the Institute of Electronics, Information and Communication Engineers, 1990. FIG. 22 shows the structure of the encoding circuit described in this literature. In FIG. 22, the reference numeral 101 represents an image buffer memory for converting the image data which are input with the data for one line as a unit into blocks of data (X11 to X44), each block having 4 .times.4 pixels, 102 a maximum and minimum representative tone level threshold value computing means for extracting the maximum tone level (L.sub.max) and the minimum tone level (L.sub.min) in the block and computing the threshold values (P2, P1) for obtaining the maximum.multidot.minimum representative tone levels, 103 a reference level.multidot.difference computing means for obtaining the maximum and minimum representative tone levels (Q4, Q1) on the basis of the image data of the block (X11 to X44) and the threshold values (P2, P1) and further obtaining the reference level (LA) and the difference (LD), 104 a quantized threshold value computing means for computing the quantized threshold values (L2, L1) from the reference level (LA) and the difference (LD), 105 a resolution information computing means for quantizing the image data (X11 to X44) on the basis of the quantized threshold values (L2, L1) and the reference level (LA) and obtaining resolution information (.phi.11 to .phi.44), and 106 an encoded data buffer for storing the reference level (LA), the difference (LD) and the resolution information (.phi.11 to .phi.44) and serially outputting them as encoded data.
The following formulas (1) to (9) show the encoding algorithm in the encoding circuit. The encoding method will now be explained with reference to these formulas and FIG. 22.
Encoding algorithm: EQU P1=(L.sub.max +3 L.sub.min)/4 (1) EQU P2=(3L.sub.max +L.sub.min)/4 (2) EQU Q1=Average value of (Xij.ltoreq.P1) (3) EQU Q4=Average value of (Xij&gt;P2) (4) EQU LA=(Q1+Q4)/2 (5) EQU LD=(Q4-Q1) (6) EQU L1=LA-LD/4 (7) EQU L2=LA+LD/4 (8) EQU for (i=1 to 4) for (j=1 to 4) if Xij.ltoreq.L1 .phi.ij=01 (binary) else if Xij.ltoreq.LA .phi.ij=00 (binary) else if Xij.ltoreq.L2 .phi.ij=10 (binary) else .phi.ij=11 (binary) end.sub.-- for end.sub.-- for(9)
The maximum and minimum representative tone level threshold value computing means 102 first extracts the maximum tone level (L.sub.max) and the minimum tone level (L.sub.min) of the pixels Xij (i, j=1 to 4) in the block output from the image buffer memory 1 and computes the threshold values (P2, P1) in accordance with the formulas (1) and (2). Then the reference level.multidot.difference computing means 103 obtains the maximum and minimum representative tone levels (Q4, Q1) in accordance with the formulas (3) and (4), and computes the reference level (LA) and the difference (LD) in accordance with the formulas (5) and (6). The quantized threshold value computing means 104 computes the quantized threshold values (L2, L1) in accordance with the formulas (7) and (8). The resolution information computing means 105 then quantizes the image data (X11 to X44) on the basis of the quantized threshold values (L2, L1) in accordance with the formula (9) and computes the resolution information (.phi.11 to .phi.44). Finally, the reference level (LA), the difference (LD) and the resolution information (.phi.11 to .phi.44) stored in the encoded data buffer 106 are serially output as the encoded data.
If it is assumed that the tone level of an image is represented by 8 bits (0 to 255), according to this encoding method, the encoded data in each block is composed of the reference level LA of 8 bits, the difference LD of 8 bits and the resolution information (.phi.11 to .phi.44) of 32 bits, making 48 bits in total, as shown in FIG. 25. Since one block has 8 bits.times.4.times.4, the compression ratio is 128/48=8/3.
The decoding method in the literature will now be explained. FIG. 23 shows the structure of the decoding circuit described in this literature. In FIG. 23, the reference numeral 111 represents an encoded data buffer for storing the encoded data and outputting them in the form of the reference level (LA), the difference (LD) and the resolution information (.phi.11 to .phi.44), 112 a representative tone level computing means for obtaining the representative tone levels (Q1 to Q4) from the reference level (LA) and the difference (LD), 113 a representative tone level allotting means for reproducing the block image data (Y11 to Y44) on the basis of the representative tone levels (Q1 to Q4) and the resolution information (.phi.11 to .phi.44), and 114 an image buffer memory for storing the reproduced block data and outputting the image data for each line.
The following formulas (10) to (14) show the decoding algorithm in this decoding circuit. The decoding method will now be explained with reference to these formulas and FIG. 23.
Decoding algorithm: EQU Q1=LA-LD/2 (10) EQU Q2=LA-LD/6 (11) EQU Q3=LA+LD/6 (12) EQU Q4=LA+LD/2 (13) EQU for (i=1 to 4) for (j=1 to 4) if .phi.ij=01 Yij=Q1 else if .phi.ij=00 Yij=Q2 else if .phi.ij=10 Yij=Q3 else Yij=Q4 end.sub.-- for end.sub.-- for(14)
The representative tone level computing means 112 first computes the representative tone levels (Q1 to Q4) from the reference level (LA) and the difference (LD) output from the encoded data buffer 111 in accordance with the formulas (10) to (13). The representative tone level allotting means 113 then reproduces the block image data (Y11 to Y44) from the resolution information (.phi.11 to .phi.44) in accordance with the formula (14) and writes the reproduced data into the image buffer memory 114. The image buffer memory 114 finally outputs the reproduced block data for each line. Each pixel of the thus-reproduced data has one of the representative tone levels (Q1 to Q4) which are arranged at regular intervals as shown in FIG. 24.
According to the decoding method having the above-described structure, since the image data are reproduced so as to have the representative tone levels constantly arranged at regular intervals without the distributed state of the tone levels of the image taken into any consideration, the picture quality is sometimes deteriorated. In addition, since it is presupposed that the representative tone levels are arranged at regular intervals, the division processings such as the formulas (11) and (12) are necessary, which leads to the problems such as a low processing speed and a large circuit scale.
Furthermore, since the threshold values for obtaining the maximum representative tone level and the minimum representative tone level are set by internally dividing the interval between the maximum tone level and the minimum tone level of the pixels in the block by a fixed ratio, as represented by the formulas (1) and (2), without the distributed state of the tone levels of the image being taken into consideration at all, when the difference between the maximum tone level and the minimum tone level of the pixels in the block is large, if the distribution width of the tone levels in the image data in the range represented by the maximum or minimum representative tone level is large, the deterioration of the picture quality is considerable.